package com.gitee.huxing.algorithmic.sort;

import java.util.HashMap;

/**
 * @Description: 二分法排序
 * @ProjectName: AlgorithmicPactice
 * @Package: com.gitee.huxing.algorithmic.sort
 * @ClassName: TwoPoints
 * @Author: huxing
 * @DateTime: 2022-01-11 5:29 PM
 */
public class TwoPoints {

    public static void main(String[] args) {

        int[] a = new int[]{1, 3, 4, 5, 6, 8, 8, 8, 11, 18};
        // 查询第一个值等于给定值的元素下标
        System.out.println(bsearchFirst(a, 10, 8));
        // 查询最后一个值等于给定值的元素下标
        System.out.println(bsearchLast(a, 10, 8));

        a = new int[]{3, 4, 6, 7, 10};
        // 查询第一个值大于等于给定值的元素下标
        System.out.println(bsearchFisrtMore(a, 5, 5));
        // 查询最后一个值小于等于给定值的元素下标
        System.out.println(bsearchLastLess(a, 5, 5));
    }

    /**
     * @Description: 二分发变形计算
     * 在一个有序数组中查找第一个值等于给定值的元素
     * @Author: huxing
     * @param a
     * @param n
     * @param value
     * @return int
     * @Date: 2022/1/11 5:57 PM
     **/
    public static int bsearchFirst(int[] a, int n, int value){
        int low = 0;
        int high = n - 1;
        while (low <= high){
            // 计算中间节点 (high - low) >> 1 这个是位运算 等同于 (high - low) /2
            // 用位运算的原因是 high和low的值可能很大，位运算能提高效率节省资源开销
            int mid = low + ((high - low) >> 1);
            if (a[mid] > value) {
                high = mid - 1;
            } else if (a[mid] < value){
                low = mid + 1;
            } else {
                if ((mid == 0) || (a[mid-1] != value)){
                    return mid;
                } else {
                    high = mid - 1;
                }
            }
        }
        return -1;
    }

    /**
     * @Description: 二分发变形计算
     * 在一个有序数组中查找最后一个值等于给定值的元素
     * @Author: huxing
     * @param a
     * @param n
     * @param value
     * @return int
     * @Date: 2022/1/11 5:57 PM
     **/
    public static int bsearchLast(int[] a, int n, int value){
        int low = 0;
        int high = n - 1;
        while (low <= high){
            // 计算中间节点 (high - low) >> 1 这个是位运算 等同于 (high - low) /2
            // 用位运算的原因是 high和low的值可能很大，位运算能提高效率节省资源开销
            int mid = low + ((high - low) >> 1);
            if (a[mid] > value) {
                high = mid - 1;
            } else if (a[mid] < value){
                low = mid + 1;
            } else {
                if ((mid == n-1) || (a[mid+1] != value)){
                    return mid;
                } else {
                    high = mid - 1;
                }
            }
        }
        return -1;
    }

    /**
     * @Description: 二分发变形计算
     * 在一个有序数组中查找第一个值大于给定值的元素
     * @Author: huxing
     * @param a
     * @param n
     * @param value
     * @return int
     * @Date: 2022/1/11 5:57 PM
     **/
    public static int bsearchFisrtMore(int[] a, int n, int value){
        int low = 0;
        int high = n - 1;
        while (low <= high){
            int mid = low + ((high - low) >> 1);
            if (a[mid] >= value) {
                if ((mid == 0) || (a[mid-1] < value)){
                    return mid;
                } else {
                    high = mid - 1;
                }
            } else{
                low = mid + 1;
            }
        }
        return -1;
    }

    /**
     * @Description: 二分发变形计算
     * 在一个有序数组中查找最后一个值小于给定值的元素
     * @Author: huxing
     * @param a
     * @param n
     * @param value
     * @return int
     * @Date: 2022/1/11 5:57 PM
     **/
    public static int bsearchLastLess(int[] a, int n, int value){
        int low = 0;
        int high = n - 1;
        while (low <= high){
            // 计算中间节点 (high - low) >> 1 这个是位运算 等同于 (high - low) /2
            // 用位运算的原因是 high和low的值可能很大，位运算能提高效率节省资源开销
            int mid = low + ((high - low) >> 1);
            if (a[mid] > value) {
                high = mid - 1;
            } else{
                if ((mid == n-1) || a[mid + 1] > value){
                    return mid;
                } else {
                    low = mid + 1;
                }
            }
        }
        return -1;
    }
}
